// Time:  O(n)
// Space: O(1)
#include <cassert>

#include <vector>
class Solution {
public:
    int maxProfit(std::vector<int> &prices) {
        int result = 0, min_price = INT_MAX;
        for (const auto& price : prices) {
            min_price = std::min(min_price, price);
            result = std::max(result, price - min_price);
        }
        return result;
    }
};

int main() {
    std::vector<int> prices = {7, 1, 5, 3, 6, 4};
    Solution sol;
    assert(sol.maxProfit(prices) == 5);
    return 0;
}